/*
 *     Author : Kashyap.R.Puranik
 *              Rajkishan G
 *              Adhiraj Alai
*/

// TODO: Delete this crap
//  coding RULES
// finish ur code only in this file and use only this class
// no global variables
// all variables and functions should be inside ur class
// parameter of run should not change


#include <iostream>
#include <vector>
#include <stack>
#include <time.h>

#define EMPTY_ 0
using namespace std;

#define ROW_SIZE 8
#define COL_SIZE 8

typedef struct move move;
// The node structure for the minimax graph
struct Node2
{
    move prevMove;                      // The move of this node w.r.t parent
    long long int eval;                 // Current best evaluated value
    bool minMax;                        // 0 if min node 1 if max

    Node2 *parent; // A pointer to the parent
    vector<struct Node2> child;            // A pointer to the child
    Node2() {eval = -65535;}
};
typedef struct Node2 node2;


// TODO: change the name of the following class and delete the comments
// class name G_(groupno) ex: G_2
class G_2
{
    private:
        /// Private data
        int board [ROW_SIZE][COL_SIZE];              //The board
        int timeLimit ;                              // Timer in milli sec

        // The move numer
        // This is required to keep track of the progress of the game
        // You can use book moves for small move numbers and
        // greedy strategies for large move numbers
        int moveNumber;
        // The max depth of the tree till which we are willing to search
        int MAX_DEPTH;
        // The preference you give to capturing a corner
        // Corners cannot be recaputred, capturing a corner may yeild good benefits
        long long int CORNER_PREF;
        // we prefer to capture blocks on edges in the later stages of the game
        // And leave it untouched in the initial part of the game
        long long int EDGE_PREF;
        // The preference you give to the number of moves your opponent has
        // Lesser the moves your opponent has better.
        long long int OPPN_MOVES_PREF;
        // In the later stages of the game,
        // we need more blocks to be occupied, (greedy)
        // In the middle stages, we prefer to have lesser number of blocks
        long long int CHIP_DIFF_PREF;
        // Getting the last move in every empty region in the end-game
        long long int PARITY_PREF;
	//mobility preference
	long long int MOBILITY_PREF;
        // The current best solution
        long long int currentBest;
        // The root node and a vector containing only the root node
        vector<node2> rootList;
        node2 root;
        node2 *currBestChild;
        // The color of our chips
        int color;
        int oppnColor;
        /// Private Functions
        // Returns number of our chips - number of opponent chips in the board
        // int ** board is the board matrix
        int chipDifference(const int (&boardCopy)[ROW_SIZE][COL_SIZE]);
        // Evaluation function
        // Uses the PREF parameters and evaluates current state
        // vector<node>::iterator leaf -> The leaf required for evaluation
        long long int eval(node2 *leaf);
        // Performs the minimax search from the given node, recursively
        // node* root -> the root of the search
        // int depth  -> The depth till which we have to search
        void minimax (node2 *myNode, int depth);
        
        // Takes in a matrix and manipulates it by applying moves
        // int  (&boardCopy)[][] -> The current state of the board after applying previous moves
        // moves      -> Stack of moves to be applied
        void applyMoves(int (&boardCopy)[ROW_SIZE][COL_SIZE], stack<move> moves);
        // Takes in a matrix and manipulates it by applying a move
        // int (&boardCopy)[][] -> The current state of the board after applying this move
        // i,j     -> coordinates of move
        void applyMove(int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j,bool minmax);

        // Generate the moves of the current node and put it in the child vector
        // Takes in an iterator pointing to the current Node
        void moveGen( node2 *myNode);
        
        //Finds the 'length'(number) of opponent's stones captured :P
        int length(const int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j, int inc_i, int inc_j,int oppColor);
        
        //checks validity of move
        int isValidMove(const int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j,bool minMax);

	//count possible legal moves
	
        int nLegalMoves(node2 *leaf);
        //may be called repeatedly by applyMove along diff directions
        void change(int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j, int inc_i, int inc_j, int len,int col);

    public:
        /// Punlic Data
        // None
        /// Public Functions
        //  constructor
        G_2() { moveNumber = 0; currentBest = -1; MAX_DEPTH = 5;CHIP_DIFF_PREF = 1;MOBILITY_PREF = 10;}
        // driver function
        void run(int  board[ROW_SIZE][COL_SIZE], int time , int mycolor, move * myMove);
};

void G_2::run(int board[ROW_SIZE][COL_SIZE], int time , int mycolor, move * myMove)
{
#ifdef DEBUG
    // print details
    cout <<time<<"\n i am player two \n ";

    for (int j=0; j<COL_SIZE; j++) { cout << "  "<<j; }
    cout <<"\n";                    // print column numbers at top
    for ( int i=0; i<ROW_SIZE; i++)
    {
        cout << i;                  // print row numbers at left
        for (int j=0; j<COL_SIZE; j++) { cout << "  "<<board[i][j];}
        cout << "\n";
    }
#endif

    // local copy of the board
    for (int i = 0 ; i< ROW_SIZE ; i ++ )
    {
        for (int j = 0 ; j< ROW_SIZE ; j ++ )
        {
            this->board[i][j] = board[i][j];
        }
    }
    this->color = mycolor;
    oppnColor = (this->color == BLUE) ? RED : BLUE;

    // Initialise root
    rootList.clear();             // Clear the root vector
    root.child.clear();           // Clear the root's children
    root.prevMove.x_pos = -1;             // Root has no parent, therefore there is
    root.prevMove.y_pos = -1;             // No move which led to it from its parent
    root.minMax = true;               // Root is a max node
    root.eval = - 65535;
    rootList.push_back(root);
    //X rootList.begin();             // Root's parent is itself

    // Root initialisation done
    // Start the minimax search from the root
    minimax(&rootList[0], MAX_DEPTH);       // Start search at root
    //To check if no move is possible;have to return (-1, -1) by rules
    if ((rootList.front().child).empty())
    {
	    move retMove= { -1, -1};
	    *myMove = retMove;
    }
    else
    {
        *myMove = currBestChild->prevMove;
    }
}

long long int G_2::eval(node2* leaf)
{
    int boardCopy[8][8];
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            boardCopy[i][j] = this->board[i][j];
        }
    }
    stack<move> moves;
    //cout<<"Entering while loop\n";
    while ( (*leaf).prevMove.x_pos != -1 )
    {
        // This should be applied in the reverse order by using a stack of moves
        moves.push((*leaf).prevMove);
        leaf = (*leaf).parent;
    }
    applyMoves( boardCopy, moves);
    // return product of constants * appropriate values that we have
    int chipDiff = chipDifference(boardCopy);
    long long int eval = (CHIP_DIFF_PREF*(moveNumber + 1) * chipDiff)/100;
    if(!leaf->minMax)
	    cout<<"BUGGGGG\n";
    eval += (100*MOBILITY_PREF*nLegalMoves(leaf))/(moveNumber+1);
    
    return (eval);
}

// Takes a node and fills in its child vector with its children
void G_2::moveGen( node2 *root)
{

    root->child.clear();
    //First get curr board pos at this root node; to find children
    int boardCopy[8][8];
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            boardCopy[i][j] = this->board[i][j];
        }
    }
    stack<move> moves;
    node2 *rootTemp = root;
    while ( rootTemp ->prevMove.x_pos != -1 )
    {
        // This should be applied in the reverse order by using a stack of moves
//	cout<<"Applying move \n";
        moves.push(rootTemp->prevMove);
        rootTemp = rootTemp->parent;
    }
    applyMoves(boardCopy, moves); 
    int ctr = 0;
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            if(boardCopy[i][j] == EMPTY_)
            {
		if (isValidMove(boardCopy, i, j,root->minMax))
                {  
                    node2 ch;
                    ch.minMax = (root->minMax) ? false: true;
                    (ch.prevMove).x_pos = i;
                    (ch.prevMove).y_pos = j;
                    ch.parent = root;
                    root->child.push_back(ch);
		    ctr++;
                }

            }
        }
    }  
//    cout<<ctr<<" Valid moves found\n";
    

    // Initialisation of each child
    // 1.> clear its child
    // 2.> set move as the move it has to take from the parent
    // 3.> set parent as the parameter to this function (i.e. root)
    // 4.> set "minimax = !(root->minimax);"
    // 6.> push it in the parents
    // put all children in the node->child
}

int G_2::nLegalMoves(node2 *root)
{
   //root->child.clear();
    //First get curr board pos at this root node; to find children
    int boardCopy[8][8];
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            boardCopy[i][j] = this->board[i][j];
        }
    }
    stack<move> moves;
    node2 *rootTemp = root;
    while ( rootTemp ->prevMove.x_pos != -1 )
    {
        // This should be applied in the reverse order by using a stack of moves
//	cout<<"Applying move \n";
        moves.push(rootTemp->prevMove);
        rootTemp = rootTemp->parent;
    }
    applyMoves(boardCopy, moves); 
    int ctr = 0;
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            if(boardCopy[i][j] == EMPTY_)
            	if (isValidMove(boardCopy, i, j,root->minMax))
                	ctr++;
	}
    }  
    return ctr;
}
// The minimax function, finds the best solution to the
void G_2::minimax (node2 *myNode, int depth)
{
    vector<node2>::iterator iter;          // iterator for the child vector
   // Base case
    if ( ! depth )
    {
        long long int value = eval(myNode);
        myNode -> eval = value;
	return;
    }
    moveGen(myNode);                   // Get the children of the current node
    //Just look at this insane bug
    //cout<<"Depth outside for loop is "<<depth<<endl;
    // Recursive call, For all children do the following
    //cout<<myNode->child.size();
    /*if(myNode->minMax)
	    cout<<"MAX NODE\n";
    else
	    cout<<"MIN NODE\n";*/
    //cout<<"In min max depth ="<<depth<<endl;
    if(myNode->child.size() == 0)
    {
	    myNode->eval = eval(myNode);
	    return;
    }
    int evalF = -65535;
    vector<node2 *>currBestChildVector;
    for (int i=0;i<myNode->child.size();i++)
    {    
	//if(depth == 4)
		//cout<<myNode->child[i].prevMove.x_pos<<","<<myNode->child[i].prevMove.y_pos<<" : CHILD AT DEPTH 4\n";
	//cout<<"Recursive call to "<<(depth - 1)<<endl;
        minimax ( &(myNode->child[i]), depth -1 );    // Depth first search
	//cout<<"Back to depth "<<depth<<endl;
        if ( myNode -> minMax )
        {   // max node
	    if ( myNode->child[i].eval >= evalF || evalF == -65535 )
            {
		if(myNode->child[i].eval > evalF && depth == MAX_DEPTH)
			currBestChildVector.clear();
                evalF = myNode->child[i].eval;
                //only update currbestchild in this block as we are max node at root.
		if(depth == MAX_DEPTH)
                	currBestChildVector.push_back(&(myNode->child[i]));
            }
        }
        else
        {   // min node
            if ( myNode->child[i].eval < evalF || evalF == -65535 )
            {
                evalF = myNode->child[i].eval;
            }
        }
    }
    if(depth == MAX_DEPTH){
    myNode->eval = evalF; 
    srand(time(NULL));
    int index = rand()%currBestChildVector.size();
    currBestChild = currBestChildVector[index];
    }

}

// returns the chip difference between the two teams
int G_2::chipDifference(const int (&board) [ROW_SIZE][COL_SIZE] )
{
    int mine = 0, opponent = 0, empty = 0;              // count of chips
    for ( int i=0; i<ROW_SIZE; i++)
    {
        for (int j=0; j<COL_SIZE; j++)
        {
            if ( board[i][j] == this->color ) mine ++;      // our color
            else if ( board[i][j] == EMPTY_ ) empty ++; // empty
            else opponent ++;                           // opponent
        }
    }
    return (mine - opponent);
}

void G_2::applyMoves(int (&boardCopy)[ROW_SIZE][COL_SIZE], stack<move> moves)
{
    move temp;    
    bool minmax = false;
    while(!moves.empty())
    {
        temp = moves.top();
        moves.pop();
        applyMove(boardCopy, temp.x_pos, temp.y_pos,!minmax);
	minmax = !minmax;
    }
}

void G_2::applyMove(int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j,bool minmax)
{
    int len =0;
    int oppColor,col;
    if(minmax)
    {
	    oppColor = oppnColor;
	    col = color;
    }
    else
    {
	    oppColor = color;
	    col = oppnColor;
    }
    if(i>-1 && j>-1 && i<ROW_SIZE && j<COL_SIZE)
    {
        if( boardCopy[i][j] != EMPTY)
            return ;

        if( (i-1)>-1 && (j-1)>-1)		// move left up
            if( boardCopy[i-1][j-1] == oppColor)
            {
                len = length(boardCopy, i, j, -1, -1,oppColor);
                if(len>0)
                    change(boardCopy, i, j, -1, -1, len,col);
            }

        if( (i-1)>-1)				//move up
            if( boardCopy[i-1][j] == oppColor)
            {
                len = length(boardCopy, i, j, -1, 0,oppColor);
                if(len>0)
                    change(boardCopy, i, j, -1, 0, len,col);
            }

        if( (i-1)>-1 && (j+1) < COL_SIZE)	//move right up
            if( boardCopy[i-1][j+1] == oppColor)
            {
                len = length(boardCopy,i, j, -1, 1,oppColor);
                if(len >0)
                    change(boardCopy,i, j, -1, 1, len,col);
            }

        if( (j+1) < COL_SIZE )			//move right
            if( boardCopy[i][j+1] == oppColor)
            {
                len =length(boardCopy, i, j, 0, 1,oppColor);
                if(len >0)
                    change(boardCopy, i, j, 0, 1, len,col);
            }

        if( (i+1)<ROW_SIZE && (j+1) < COL_SIZE)	//move right down
            if( boardCopy[i+1][j+1] == oppColor)
            {
                len = length(boardCopy, i, j, 1, 1,oppColor);
                if(len >0)
                    change(boardCopy, i, j, 1, 1, len,col);
            }

        if( (i+1)<ROW_SIZE )			//move down
            if( boardCopy[i+1][j] == oppColor)
            {
                len =	length(boardCopy, i, j, 1, 0,oppColor);
                if(len >0)
                    change(boardCopy, i, j, 1, 0, len,col);
            }


        if( (i+1)< ROW_SIZE && (j-1) > -1 )	//move left down
            if( boardCopy[i+1][j-1] == oppColor)
            {
                len =length(boardCopy, i, j, 1, -1,oppColor);
                if(len >0)
                    change(boardCopy, i, j, 1, -1, len,col);
            }

        if( (j-1) > -1)				//move left
            if( boardCopy[i][j-1] == oppColor )
            {
                len = length(boardCopy, i, j, 0, -1,oppColor);
                if(len >0)
                    change(boardCopy, i, j, 0, -1, len,col);
            }

	if(minmax)
        	boardCopy[i][j] = this->color;
	else
		boardCopy[i][j] = this->oppnColor;
        return ;
    }
    else
        return ;

}

//----------------------------------------------------
//	purpose: check the move
//
//	input: 	i,j of the move ;
//	ouput: 	0 	if not valid
//		>0	if valid move
//----------------------------------------------------

int G_2::isValidMove(const int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j,bool minMax)
{
    int len = 0;
    int oppColor;
    if(minMax)
    	 oppColor = oppnColor;
    else
	 oppColor = color;
    if(i>-1 && j>-1 && i<ROW_SIZE && j<COL_SIZE)
    {
        if( (i-1)>-1 && (j-1)>-1)		// move left up
        if( boardCopy[i-1][j-1] == oppColor)
            len += length(boardCopy, i, j, -1, -1,oppColor);


        if( (i-1)>-1)				//move up
        if( boardCopy[i-1][j] == oppColor)
            len += length(boardCopy, i, j, -1, 0,oppColor);

        if( (i-1)>-1 && (j+1) < COL_SIZE)	//move right up
        if( boardCopy[i-1][j+1] == oppColor)
            len += length(boardCopy, i, j, -1, 1,oppColor);

        if( (j+1) < COL_SIZE )			//move right
        if( boardCopy[i][j+1] == oppColor)
            len +=length(boardCopy, i, j, 0, 1,oppColor);

        if( (i+1)<ROW_SIZE && (j+1) < COL_SIZE)	//move right down
        if( boardCopy[i+1][j+1] == oppColor)
            len += length(boardCopy, i, j, 1, 1,oppColor);

        if( (i+1)<ROW_SIZE )			//move down
        if( boardCopy[i+1][j] == oppColor)
            len +=	length(boardCopy, i, j, 1, 0,oppColor);

        if( (i+1)<ROW_SIZE && (j-1) > -1)	//move left down
        if( boardCopy[i+1][j-1] == oppColor)
            len +=length(boardCopy, i, j, 1, -1,oppColor);

        if( (j-1) >-1)				//move left
        if( boardCopy[i][j-1] == oppColor )
            len += length(boardCopy, i, j, 0, -1,oppColor);

        return len;
    }
    else return 0;
}

int G_2::length(const int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j, int inc_i, int inc_j,int oppColor)
{
    int length = 0;
    int initi=i,initj=j;
   i = i + inc_i;
    j = j + inc_j;
   
    while(1)
    {
        if(i>-1 && j>-1 && i<ROW_SIZE && j<COL_SIZE)
        {
            if(boardCopy[i][j]==oppColor)
            {
                length++;

                i += inc_i;
                j += inc_j;
            }

            else if(boardCopy[i][j]==EMPTY)
                return 0;

            else
	    {
                return length;
	    }
        }
        else
            return 0;

    }
    return 0;
}

//----------------------------------------------------
//	purpose: change the color on the board
//
//	input: i,j of the move ; (inc_i, incr_j)diretion; length ; color
//	ouput: none
//----------------------------------------------------

void G_2::change(int (&boardCopy)[ROW_SIZE][COL_SIZE], int i, int j, int inc_i, int inc_j, int len,int col)
{
    int p_i = i+inc_i;
    int p_j = j+inc_j;

    while(len>0)
    {
        if(!(i>-1 && j>-1 && i<ROW_SIZE && j<COL_SIZE))
        {
            cout << "\nerror: wronge i ,j\n";
            return;
        }

        boardCopy[p_i][p_j] = col;
        len--;
        p_i = p_i +inc_i;
        p_j = p_j +inc_j;
    }

}


